//611.有效三角形的个数
import java.util.Arrays;

class Solution1 {
    public int triangleNumber(int[] nums) {
        //1.优化 排序
        Arrays.sort(nums);
        //2.利用双指针
        int n = nums.length;
        int ret = 0;//统计个数
        //2.1 先固定最大值
        for(int i = n-1;i >= 2;i--){
            //2.2 利用双指针快速统计出符合要求的三个元组个数
            int left = 0;
            int right = i-1;
            while(left < right){
                if((nums[left]+nums[right]) >nums[i]){
                    ret += right-left;
                    right --;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }
}